Биномиальный коэффициент

Биномиальные коэффициенты — коэффициенты в разложении $(1+x)^n$ по степеням $x$ (т. н. бином Ньютона): $$(1+x)^n = {n\choose 0} + {n\choose 1}x + {n\choose 2}x^2 + \cdots = \sum_k {n\choose k} x^k.$$ Значение биномиального коэффициента ${n\choose k}$ определено для всех целых чисел $n$ и $k$. Явные формулы для вычисления биномиальных коэффициентов: $${n\choose k} = \frac{n!}{k!\;(n-k)!}= \frac{n(n-1)(n-2)...(n-k+1))}{k!}$$для $0\leq k \leq n$; $${n\choose k} = 0$$для $k$ или $0\leq n < k$; $${n\choose k} = (-1)^k {-n+k-1\choose k}$$для $n$,

где $n!$ и $k!$ — факториалы чисел $n$ и $k$.

Биномиальный коэффициент ${n\choose k}$ является обобщением числа сочетаний $C^k_n$, которое определено только для неотрицательных целых чисел $n$, $k$.

Биномиальные коэффициенты часто возникают в комбинаторных задачах и теории вероятностей.

Обобщением биномиальных коэффициентов являются мультиномиальные коэффициенты.

Треугольник Паскаля

Тождество $${n\choose k}={n-1\choose k-1} + {n-1\choose k}$$ позволяет расположить биномиальные коэффициенты для неотрицательных $n$, $k$ в виде треугольника Паскаля, в котором каждое число равно сумме двух вышестоящих: $$\begin{matrix}n=0: & & & & & 1 & & & &\\n=1: & & & & 1 & & 1 & & &\\n=2: & & & 1 & & 2 & & 1 & &\\n=3: & & 1 & & 3 & & 3 & & 1 &\\n=4: & 1 & & 4 & & 6 & & 4 & & 1\\\vdots & & \vdots & & \vdots & & \vdots & & \vdots &\end{matrix}$$

Треугольная таблица, предложенная Паскалем в «Трактате об арифметическом треугольнике» (1654), отличается от выписанной здесь поворотом на 45°. Таблицы для изображения биномиальных коэффициентов были известны и ранее.

Свойства

Интересно, что если рассмотреть ряды в треугольнике Паскаля, состоящие из биномиальных коэффициентов, то в пределе получим функцию нормального распределения - распределение Гаусса.

Тождества

1. ${n\choose k} = {n-1\choose k-1} + {n-1\choose k}$
2. ${n\choose k} = {n\choose n-k}$ (правило симметрии)
3. ${n\choose 0} + {n\choose 1} + \cdots + {n\choose n} = 2^n$
4. ${n\choose 0} + {n\choose 2} + \cdots + {n\choose 2\lfloor n/2\rfloor} = 2^{n-1}$
5. ${n\choose 0}^2 + {n\choose 1}^2 + \cdots + {n\choose n}^2 = {2n\choose n}$
6. $\sum_{k=0}^n{r\choose m+k}{s\choose n-k}={r+s\choose m+n}$ (свёртка Вандермонда)

Асимптотика и оценки

1. ${2n\choose n}\sim \frac{2^{2n}}{\sqrt{\pi n}}$
2. $\sum^{m}_{k=0}{n\choose k}\le \frac{n}{(n/2-m)^2}2^{n-3}$ при $m\le n/2$ (неравенство Чебышёва)
3. $\sum^{m}_{k=0}{n\choose k}\le 2^{nH(m/n)}$ (энтропийная оценка), где $H(x)=-x\log_2x-(1-x)\log_2(1-x)$ — энтропия.
4. $\sum^{n/2-\lambda}_{k=0}{n\choose k} \le 2^ne^{-2\lambda^2/n}$ (неравенство Чернова)

Алгоритмы вычисления биномиальных коэффициентов

Биномиальные коэффициенты могут быть вычислены с помощью формулы ${n\choose k}={n-1\choose k}+{n-1\choose k-1}$, если на каждом шаге хранить значения ${n\choose k}$ при $k=0,1,\dots,n$. Этот алгоритм особенно эффективен, если нужно получить все значения ${n\choose k}$ при фиксированном $n$. Алгоритм требует $O(n)$ памяти ($O(n^2)$ при вычислении всей таблицы биномиальных коэффициентов) и $O(n^2)$ времени (в предположении, что каждое число занимает единицу памяти и операции с числами выполняются за единицу времени).

Второй способ основан на тождестве ${n\choose k}=\frac{n}{n-k}{n-1\choose k}$. Он позволяет вычислить значения ${n\choose k}$ при фиксированном $k$. Алгоритм требует $O(1)$ памяти ($O(l)$ если нужно посчитать $l$ последовательных коэффициентов с фиксированным $k$) и $O(k)$ времени.

См. также

• Биномиальное распределение

Ссылки

• О. В. Кузьмин. Треугольник и пирамида Паскаля: свойства и обобщения, СОЖ, 2000, No 5, с. 101–109.